我要招人

去企业版

首页 > 试题广场 >

缺失的第一个正整数

[编程题]缺失的第一个正整数

热度指数：76755 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

数据范围:

$-2^{31}\le nums[i] \le 2^{31}-1$

$0\le len(nums)\le5*10^5$

示例1

输入

[1,0,2]

输出

示例2

输入

[-2,3,4,1,5]

输出

示例3

输入

[4,5,6,8,9]

输出

算法知识视频讲解

Python 3

pzq

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # 方法一: 快速查找考虑用hash表
        tab_hash = {val:1 for val in nums}
        for i in range(1, len(nums) + 2):
            val = tab_hash.get(i)
            if val is None:
                return i

        # 方法二: 排序
        def minNumberDisappeared(self , nums: List[int]) -> int:
            # write code here
            nums.sort()
            ind = 0
            for i in range(1, len(nums) + 2):
                if i > nums[-1]:
                    return i
                while True:
                    if i == nums[ind]:
                        ind += 1
                        break
                    if i > nums[ind]:
                        ind += 1
                    if i < nums[ind]:
                        return i

发表于 2023-05-18 22:17:59 回复(0)

Python 3

牛客999581607号

https://www.youtube.com/watch?v=8g78yfzMlao

发表于 2022-09-18 22:20:57 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        n=len(nums)
        d=dict()
        for i in range(n):
            num=nums[i]
            if not d.get(num) and num>0:
                d[num]=1
        for i in range(1,n+2):#从1到n+1中找，而不是[1,n]
            if not d.get(i):
                return i

发表于 2022-08-20 16:06:49 回复(0)

Python 3

牛客805839264号

class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
# write code here
n=len(nums)
mp={}
for i in range(n):
mp[nums[i]]="0" # it was no matter about the value

res=1
while res in mp:
res+=1
return res

发表于 2022-08-19 10:48:58 回复(0)

Python 3

南风不竞--

不使用hash表，仅对数组本身进行遍历

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # 排序
        nums.sort()
        # 遍历列表，找到第一个大于0的元素
        for i in range(len(nums)):
            if nums[i] <=0:
                continue
            else:
                id = i
                break
        # 如果该元素大于1，直接返回1
        if nums[id] > 1:
            return 1
        # 否则，继续遍历，当第i个元素与第i+1个元素不相等，且不连续时，输出nums[i]+1
        for i in range(id,len(nums)-1):
            if nums[i]!= nums[i+1] and nums[i]+1 != nums[i+1]:
                return nums[i]+1
        # 最坏的情况，遍历完整个数组
        return nums[-1]+1

发表于 2022-08-11 16:11:07 回复(0)

Python 3

Vivimore

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        nums = set(nums)
        for i in range(1, len(nums)+2):
            if i not in nums:
                return i

发表于 2022-06-18 20:50:36 回复(1)

Python 3

宫城良田z

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        num_set = set(nums)
        res = 1
        while True:
            if res not in num_set:
                return res
            res += 1

发表于 2022-04-28 10:40:03 回复(0)

Python 3

绝世这天下

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
list01 = []
for i in range(len(nums)):
if nums[i]>0:
list01.append(nums[i])
list01.sort()
for i in range(len(list01)-1):
if list01[0]!=1:
return 1
if list01[i+1]-list01[i] >=2:
return list01[i]+1
return list01[i+1]+1

发表于 2022-03-25 00:23:25 回复(0)

Python 3

路痴喵

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        
        if len(nums) == 0:
            return 1
        elif 1 not in nums:
            return 1
        else:
            nums.sort()
            t = nums.index(1)
            tmp = nums[t:]
            for i in range(len(tmp)-1):
                if tmp[i]+1 != tmp[i+1]:
                    return tmp[i]+1
            return tmp[-1]+1

发表于 2022-03-21 23:40:32 回复(0)

Python 3

Virtual~

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        from collections import defaultdict
        
        record = defaultdict(int)
        for i in nums:
            record[i] += 1
        
        res = 1
        while True:
            if record[res] == 0:
                return res
            res += 1

发表于 2022-03-10 16:55:04 回复(0)

Python 3

牛客343459580号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        save = 1
        nums.sort()
        for i in nums:
            if(i<=0):
                continue
            elif(i == save):
                save += 1
                continue
            else:
                #break
                return save
        return save

发表于 2022-01-28 18:54:30 回复(0)

Python 3

Joy_9

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        n=len(nums)
        for i in range(n):
            if nums[i]<0:  
                nums[i]=n+1
        if min(nums)>1:
            return 1
        v=n+min(nums)
        dp=[False]*v
        for i in nums:
            if i <=v:
                dp[i-1]=True
        for i in range(min(nums)-1,len(dp)):
            if dp[i]==False:
                return i+1
        return n

发表于 2022-01-20 07:01:16 回复(0)

Python 3

JSFaner

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        if not nums: return 1
        nums.sort()
        nums = [ i for i in nums if i > 0]
        for k,v in enumerate(nums):
            if v != k+1: return k+1
        return nums[-1]+1

发表于 2021-12-26 22:01:51 回复(0)

提交观点

问题信息

数组哈希

上传者：牛客301499号

难度：

14条回答 632收藏 4256浏览

通过挑战的用户

查看代码

牛客89418...

2022-10-27 16:32:27
牛客86531...

2022-09-16 18:53:41
Daoremi

2022-09-16 17:29:06
粗茶

2022-09-16 17:03:01
牛客13682...

2022-09-16 16:52:44

缺失的第一个正整数

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题